package tk0084.dev.google.quiz;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BfsPuzzle implements PuzzleStrategy {

	public State unpuzzle(Puzzle puzzle) {
		System.out.println("unpuzzling chars:" + puzzle.getInitialChars() + " row:" + puzzle.getRow() + " col:" + puzzle.getCol());

		List<State> currentStates = new ArrayList<State>();
		currentStates.add(State.root(new Table(puzzle.getInitialChars(), puzzle.getRow(), puzzle.getCol())));

		Set<State> allStates = new HashSet<State>();

		List<State> nextStates = new ArrayList<State>();
		int count = 0;
		while (true) {
			for (State currentState : currentStates) {
				for (State next : currentState.getNextStates()) {
					if (puzzle.isEndState(next)) {
						return next;
					}
					if (allStates.add(next)) {
						nextStates.add(next);
					}
				}
			}
			currentStates = new ArrayList<State>(nextStates);

			if (++count > 1000) {
				throw new RuntimeException("coud not resolve");
			} else {
				System.out.println(count + " " + allStates.size());
			}
		}
	}

}
